package com.cqs.leetcode.sort;

import com.cqs.leetcode.ListNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author lixiaowen
 * @create 2019-12-11
 */
public class SortList148 {


    /**
     *
     * 归并排序
     *
     * @param head
     * @return
     */
    public ListNode sortListMerge(ListNode head) {
        if (head == null || head.next == null ) return head;
        //1.找切分点
        ListNode slow = head,fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            if (fast.next != null) {
                fast = fast.next;
            }
            slow = slow.next;
        }
        ListNode slowNext = slow.next;
        slow.next = null;
        ListNode l = sortListMerge(head);
        ListNode r = sortListMerge(slowNext);
        //合并
        return merge(l,r);
    }


    private ListNode merge(ListNode l1, ListNode l2){
        if (l1 == null ) return l2;
        if (l2 == null) return l1;
        ListNode head, pre;
        if (l1.val <= l2.val) {
            head = pre =  l1;
            l1 = l1.next;
        }else {
            head = pre = l2;
            l2 = l2.next;
        }
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val){
                pre.next = l1;
                pre = l1;
                l1 = l1.next;
            }else {
                pre.next = l2;
                pre = l2;
                l2 = l2.next;
            }
        }
        if (l1 == null) pre.next = l2;
        if (l2 == null) pre.next = l1;
        return head;
    }




    //
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        //先转化为数组
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        ListNode[] nodes = new ListNode[list.size()];
        list.toArray(nodes);
        //排序

        quickSort(nodes);

        //组装成链表
        for (int i = 0; i < nodes.length - 1; i++) {
            nodes[i].next = nodes[i+1];
        }
        nodes[nodes.length - 1].next = null;
        return nodes[0];

    }


    private void quickSort(ListNode[] nodes){
        quickSort(nodes,0, nodes.length - 1);

    }

    private void quickSort(ListNode[] nodes, int left, int right){
        if (left >= right) return ;
        final int pindex = left, r = right;
        left += 1;
        while (left <= right) {
            //左侧找到第一个大于基准元素的位置
            while (left <= right && nodes[left].val <= nodes[pindex].val ){
                ++left;
            }

            while (left <= right && nodes[right].val > nodes[pindex].val ){
                --right;
            }
            //交换
            if(left < right){
               swap(nodes, left, right);
            }
        }
        //基准元素交换
        swap(nodes, pindex, right);
        quickSort(nodes,pindex, right - 1);
        quickSort(nodes, right + 1, r);
    }

    private void swap(ListNode[] nodes, int left, int right){
        //交换
        ListNode tmp = nodes[left];
        nodes[left] = nodes[right];
        nodes[right] = tmp;
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 200; i++) {
            list.add(new Random().nextInt(1000));
        }
        //System.out.println(list);

        ListNode[] nodes = new ListNode[1000];

        for (int i = 0; i < nodes.length; i++) {
            nodes[i] = new ListNode(new Random().nextInt(nodes.length));
        }

        //System.out.println(Arrays.stream(nodes).collect(Collectors.toList()));
        new SortList148().quickSort(nodes);

        //List<ListNode> listNodes = Arrays.asList(nodes);

        List<ListNode> collect = Arrays.stream(nodes).collect(Collectors.toList());
//        System.out.println(collect);

        ListNode head = new ListNode(1);
        ListNode pre = head;
        int size = 20;
        for (int i = 0; i < size; i++) {
            ListNode node = new ListNode(new Random().nextInt(5 * size));
            pre.next = node;
            pre = node;

        }
        final ListNode node = head;
        while (head != null) {
            System.out.print(head.val + "->" );
            head = head.next;
        }
        System.out.println("=========================");
        head = new SortList148().sortListMerge(node);
        while (head != null) {
            System.out.print(head.val + "->" );
            head = head.next;
        }
        System.out.println(head);



        int[] bucket = new int[26];
        bucket[25]++;
        for (int i = 0; i < bucket.length; i++) {
            System.out.println(bucket[i]);
            Map map = new HashMap();

        }
        Map<Character,Integer> map = new HashMap<>();
        Iterator<Character> iterator = map.keySet().iterator();
        while (iterator.hasNext()){
            Character next = iterator.next();
            Integer integer = map.get(next);
            if (integer == 1) {

            }
        }

    }

}
